package com.abel.day0301;

import java.util.ArrayList;

/**
 * @author xiachao
 * @date 2019/3/3
 */
public class Solution {

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2 == null){
            return false;
        }
        return isSub(root1, root2);
    }

    private boolean isSub(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }
        if(root1.val == root2.val){
            boolean match = isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
            if(match){
                return true;
            }
        }
        return isSub(root1.left, root2) || isSub(root1.right, root2);
    }

    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        TreeNode n1 = root.left;
        TreeNode n2 = root.right;
        if(n1 == null && n2 == null){
            return;
        }
        root.left = n2;
        root.right = n1;
        if(n1 != null){
            this.Mirror(n1);
        }
        if(n2 != null){
            this.Mirror(n2);
        }
    }

    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        int row = matrix.length;
        int col = matrix[0].length;

        int r = 0;
        int c = 0;
        int b = 0;
        while(ret.size() < row*col){

            while (c<col-b)ret.add(matrix[r][c++]);
            c--;
            r++;
            while (r<row-b) ret.add(matrix[r++][c]);
            r--;
            c--;
            if(ret.size() == row*col){
                break;
            }
            while (c>=b) ret.add(matrix[r][c--]);
            c++;
            r--;
            while (r>=b+1) ret.add(matrix[r--][c]);
            r++;
            c++;
            b++;
        }
        return ret;
    }

    public static void main(String[] args) {

        System.out.println(System.getProperty("sun.boot.class.path"));
        //int [][] matrix = {{1, 2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
        int [][] matrix = {{1}, {2}, {3}, {4}};
        ArrayList<Integer> ret = new Solution().printMatrix(matrix);
        for(int r : ret){
            System.out.print(r+", ");
        }
//        TreeNode n1 = new TreeNode(8);
//        TreeNode n2 = new TreeNode(8);
//        TreeNode n3 = new TreeNode(7);
//        TreeNode n4 = new TreeNode(9);
//        TreeNode n5 = new TreeNode(2);
//
//        n1.left = n2;
//        n1.right = n3;
//        n2.left = n4;
//        n2.right = n5;

        //System.out.println(new Solution().HasSubtree(n1, n2));
    }

}
